package book;

import java.util.HashMap;
import java.util.Map;

// 旅途规划问题
public class TripPlanSolution {

    // 城市类 - 表示一个城市信息
    // 这个类同时用作双向链表的节点，用于维护作为插入排序使用的队列链表
    class City {
        // 名称（标识）
        final String name;

        // 从该城市出发的相邻路径(用链表存储)
        Trip head; 

        // 从起点出发到该城市的总票价（总路径长度）
        int amount = -1; 

        City(String name) {
            this.name = name;
        }

        // 双向链表的前后指针
        City prev, next;
    }

    // 航班类（表示一条路径）
    class Trip {
        // 航班起点、终点
        final City start, end;

        // 航班票价（边权重，或称路径长度）
        final int price;

        // 单指针 - 指向同一个起点的下一条邻边
        final Trip next;

        Trip(City s, City t, int p, Trip n) {
            start = s; end = t; price = p; next = n;
        }
    }

    // 维护所有城市列表
    Map<String, City> cities = new HashMap<>();

    // 从列表获取城市，如果不在列表中则新建一个并添加
    City getCity(String name) {
        if (cities.containsKey(name)) {
            return cities.get(name);
        } else {
            City c = new City(name);
            cities.put(name, c);
            return c;
        }
    }

    // 添加航班（有向边）
    void addTrip(String start, String end, int price) {
        City startCity = getCity(start), endCity = getCity(end);
        // 创建航班对象，并使用头插法把航班添加到起点城市的邻接表中
        Trip trip = new Trip(startCity, endCity, price, startCity.head);
        startCity.head = trip;
    }

    /**
     * 用Dijkstra计算（不超预算的）所有航班路线
     * @param src 起点城市
     * @param budget 预算（即路径长度上限），超出的答案不需要返回
     * @return 返回所有预算内的目标城市及最小票价
     */
    public Map<String, Integer> findAllShortestPath(String src, int budget) {
        // 创建存放答案的容器
        Map<String, Integer> answer = new HashMap<>();

        // 初始化起点信息：创建排序链表并将起点放入为第一个元素
        City headCity = getCity(src);
        headCity.amount = 0;

        // 执行dijkstra搜索最短路径
        while (headCity != null) {
            // 取出头节点作为当前节点，输出到答案
            City s = headCity;
            headCity = headCity.next;
            answer.put(s.name, s.amount);

            // 枚举当前城市的邻接路径，发现新的路径并更新维护排序数组
            for (Trip trip = s.head; trip != null; trip = trip.next) {
                // 当前路径的目标点为t，当前总路径长度=起点到s长度+s到t的长度
                City t = trip.end;
                int newAmount = s.amount + trip.price;

                // 题目要求：不考虑超出预算的航线
                if (newAmount > budget) continue; 

                // 情形1: 该相邻点第一次访问，使用插入排序加入队列
                if (t.amount == -1) {
                    // 计算当前搜索到的路径长度（权值）
                    t.amount = newAmount;
                    // 使用头插法插入排序将该顶点加入队列
                    if (headCity == null || t.amount <= headCity.amount) {
                        if (headCity != null) {
                            t.next = headCity;
                            headCity.prev = t;
                        }
                        headCity = t;
                    } else {
                        City c = headCity;
                        while (c.next != null && c.next.amount < t.amount)
                            c = c.next;
                        t.next = c.next;
                        if (c.next != null) c.next.prev = t;
                        c.next = t;
                        t.prev = c;
                    }
                }
                // 情形2: t 之前被搜索到，且当前路径需要更新
                else if (newAmount < t.amount) {
                    // 更新旅途费用
                    t.amount = newAmount;

                    // 定位到新的排序位置
                    City c = t;
                    while (c != headCity && c.prev.amount > t.amount) 
                        c = c.prev;

                    // 执行链表位置交换
                    if (t != c) {
                        // 先将t从链表移除
                        t.prev.next = t.next;
                        if (t.next != null) t.next.prev = t.prev;
                        // 再将t插入链表（替换c的位置）
                        if (c == headCity) {
                            headCity.prev = t;
                            t.next = headCity;
                            headCity = t;
                        } else {
                            t.prev = c.prev;
                            if (t.prev != null)
                                t.prev.next = t;
                            t.next = c;
                            c.prev = t;
                        }
                    }
                }
            }
        }

        // 返回最终结果
        return answer;
    }

    public static void main(String[] args) {
        TripPlanSolution sln = new TripPlanSolution();
        sln.addTrip("广州", "长沙", 200);
        sln.addTrip("广州", "北京", 800);
        sln.addTrip("广州", "上海", 300);
        sln.addTrip("长沙", "武汉", 500);
        sln.addTrip("武汉", "北京", 100);
        sln.addTrip("上海", "武汉", 200);
        sln.addTrip("上海", "北京", 600);
        String src = "广州";
        int budget = 500;
        Map<String, Integer> ms = sln.findAllShortestPath(src, budget);
        int n = ms.size();
        System.out.println("从" + src + "出发, 预算" + budget + "元, 共有以下" + n + "个方案:");
        for (String key : ms.keySet()) 
            System.out.println("到" + key + ", 共" + ms.get(key) + "元");
    }
}
